// graphcoloring.cpp : 
//
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <string>
#include <time.h>
#include <sstream>
#include "graphcoloring.h"
#include "Chain.h"
#include "Input.h"
#include "Helpers.h"
#include "parsing\chainparser.h"
#include "parsing\inputparmetersparser.h"
#include "parsing\chainwriter.h"
#include "GreedyFillGroupAlgorithm.h"
#include "GreedyFillMaximalGroupAlgorithm.h"
#include "BreakAndRefillGroupAlgorithm.h"
#include "SwitchVerticesAlgorithm.h"
#include "filesystem.h"

using namespace std;

#ifdef _DEBUG
#undef _DEBUG
#endif

/*****************************************************************************/
// funcation declarations
/*****************************************************************************/
#ifdef _DEBUG	
void forDebug_runUnitTests();
Chain* forDebug_validateGraphState(string chainFileName, 
								   InputVariables &inputVars,set<vector<bool> >* vertices);
void forDebug_debugAlgorithems(Chain* chain, InputVariables &inputVars );
#endif

/*****************************************************************************/
// main
// Defines the entry point for the console application.
// runs the graph coloring on the given input files.
/*****************************************************************************/
int main(int argc, char* argv[])
{
	
	if (argc < 5)
	{
		Logger::LogMessage("Usage: graphcoloring.exe [parmeters file name] [chain to improve file name] [destenation chain file name] [output folder name]");
		return -1;
	}

	// wrappar logic
	try
	{
		GraphColoringManager gcm;
		WinFileSystem filesystem;
		
		//in order to create the chain directory and the debug file in it.
		string outputDirName = gcm.SetupDirectory(argv[2], argv[4]);
		Logger::ChangeLogStream(false);
		
		//in order to read the input files wich are located outside the chain
		//directory
		filesystem.NavigateUpFromCurrentDirectory(2);

		std::stringstream stream;
		stream<<"\n";
		stream<<"**************************************************"<<endl;
		stream<<"input file name is: "<< argv[1] << endl;
		stream<<"input chain file name is: "<< argv[2] << endl;
		stream<<"destenation chain file name is: " << argv[3] << endl;
		stream<<"**************************************************"<<endl;
		Logger::LogMessage(stream.str());
		stream.str("");

		gcm.ParseInputFiles(argv[1], argv[3]);
		
		set<vector<bool> >* vertices = gcm.CreateProgramVertices();
		delete vertices; //no need for this, we are using the dirctory.
		
		gcm.CreateInitialChain(argv[2]);

		//in order to output all files to the directory of the chain
		filesystem.SetTheCurrentDirectory(outputDirName);

		gcm.FillInitialChain();
		//turn on the algorithms to use for filling the chain:
		GraphColoringManager::ALGORITHMS alg =
		//	GraphColoringManager::GREEDY					;
			GraphColoringManager::IMPROVE_GROUP_WITH_GREEDY |
			GraphColoringManager::BREAK_AND_REFILL			|
			GraphColoringManager::SWITCH_SINGELS			|
			GraphColoringManager::SWITCH_PAIRS				;
		// For future use, after algorithm implementation
		//	GraphColoringManager::DUMP_GROUPS_AND_REFILL	;
		
		GraphColoringManager::COLORING_RESULT coloringRes = gcm.StartTheColoring(alg);
		gcm.OutputResult(argv[2], coloringRes);
	}
	catch(GraphColoringException *e)
	{
		Debug::PrintDebugMsg(e->GetErrorDescription());
	}
	catch(ChainParserExepetion *e)
	{
		Debug::PrintDebugMsg(e->GetErrorDescription());
	}
	catch(InputParmetersParserExepetion *e)
	{
		Debug::PrintDebugMsg(e->GetErrorDescription());
	}
	catch(ChainWriterExepetion *e)
	{
		Debug::PrintDebugMsg(e->GetErrorDescription());
	}

	return 0;
}


/*****************************************************************************/
// GraphColoringManager
// implementation of the Graph Coloring Manager functions
/*****************************************************************************/

//----------------------------------------------------------------------------
// SetupDirectory
// prepare a directory for the output files and makes it the 
// current directory.
//
// @param processForDirName
//		a string that from it the directory name will be extracted
//
// @throw GraphColoringException
//		if the directory already exists.
//----------------------------------------------------------------------------
string GraphColoringManager::SetupDirectory(string processForDirName, string containingDir)
{
//note! can only be used on windows platform.
#ifdef WIN32	
	
	WinFileSystem fileSys;
	fileSys.SetTheCurrentDirectory(containingDir);

	string dirName = CleanNameStr(processForDirName);
	
	if(!fileSys.MakeDirectory(dirName))
		throw(new GraphColoringException("failed to setup directory!"));

	fileSys.SetTheCurrentDirectory(dirName);

	containingDir += "\\" + dirName;

	return containingDir;
#endif
}

//----------------------------------------------------------------------------
// ParseInputFiles
// reads the variable input file, and the destination chain input file
// and initialize the matching members of the class.
//
// @param inputFileName
//		the name of the input variables file to parse (a *.ini file type)
// @param destenationColoringFileName
//		the name of the destination chain file to improve (a *.chain file type)
//
// @return InputVariables&
//		a reference to the InputVariables object that was created based on the
//		parsing.
//
// @throw ChainParserExepetion
//		in case the chain file parsing failed
// @throw InputParmetersParserExepetion
//		in case the input variables file parsing failed
// @throw GraphColoringException
//		for any other failure
//----------------------------------------------------------------------------
InputVariables& GraphColoringManager::ParseInputFiles(string inputFileName, string destenationColoringFileName)
{
	//read and prepare the input parmeters
	Logger::LogMessage("Parsing input parameters");
	try
	{
		WinInputParmetersParser inputParser(inputFileName);
		ChainParser destenationColoringParser(destenationColoringFileName);
		m_InputVars.ParseInputParameters(destenationColoringParser, inputParser);

		Logger::LogMessage("Input parsed successfully");

		Logger::LogMessage("###############################################################");	
		return m_InputVars;
	}
	catch(ChainParserExepetion *e)
	{
		Logger::LogMessage("chain input file parsing failed!");
		throw e;
	}
	catch(InputParmetersParserExepetion *e)
	{
		Logger::LogMessage("input parameters file parsing failed!");
		throw e;
	}
	catch(GraphColoringException *e)
	{
		Logger::LogMessage("parsing failed!");
		throw e;
	}
}

//----------------------------------------------------------------------------
// CreateProgramVertices
// creates all the vertices the program will use based on the input received.
//
// @return set<vector<bool> >*
//		a set with all the vertices names that were created.
//
// @throw GraphColoringException
//		if the vertices creation failed
//----------------------------------------------------------------------------
set<vector<bool> >* GraphColoringManager::CreateProgramVertices()
{
	//create all the vertices
	Logger::LogMessage("Creating vertex data");

	try
	{
		set<vector<bool> >* vertices = VertexDirectory::CreateAllVertices(m_InputVars.n, m_InputVars.w);
		
		if(vertices == NULL)
			throw(new GraphColoringException("failed to initiate the vertex directory!"));
		
		//add them to the VertexDirectory
		VertexDirectory::FillVertexDirectory(vertices);
		Logger::LogMessage("Vertex data loaded");

		Logger::LogMessage("###############################################################");

		return vertices;
	}
	catch(GraphColoringException *e)
	{
		Logger::LogMessage("FillVertexDirectory failed!");
		throw e;
	}
}

//----------------------------------------------------------------------------
// CreateInitialChain
// creates a chain object based on the chain input file that was passed
// (a chain that wad created in the permutation project)
//
// @param chainFileName
//		the name of the chain that was created in the permutation project
//		and is the input chain for this program
//
// @throw ChainParserExepetion
//		if the chain file parsing failed
// @throw GraphColoringException
//		if any other error occurred
//----------------------------------------------------------------------------
void GraphColoringManager::CreateInitialChain(string chainFileName)
{
	try
	{
		Logger::LogMessage("Loading chain from input");
		//create the chain
		ChainParser chainParser(chainFileName);
		m_MainChain = new Chain(chainParser, m_InputVars);
		m_MainChain->SetLastGroupFromPermutaionsIndex(m_MainChain->GetLength() - 1);

		if(ChainSanityCheck(m_MainChain, true) == false)
			throw(new GraphColoringException("failed Sanity Check! - initial chain is not legal!"));

		Logger::LogMessage("Chain loaded");
		Logger::LogMessage("###############################################################");
	}
	catch(ChainParserExepetion *e)
	{
		Logger::LogMessage("chain input file parsing failed!");
		throw e;
	}
	catch(GraphColoringException *e)
	{
		Logger::LogMessage("parsing failed!");
		throw e;
	}
	catch(std::bad_alloc *e)
	{
		e = NULL; //for avoiding compiler warning
		Logger::LogMessage("memory allocation failed in GraphColoringManager::CreateInitialChain.\nChain wasn't created.");
		throw(new GraphColoringException("memory allocation failed!"));
	}
	
}

//----------------------------------------------------------------------------
// FillInitialChain
// iterates over all the groups in the chain from the input and for each one
// fills it with more vertices using a regular greedy algorithm.
// after that, iterates over the groups again and for each one
// using the break and refill algorithm (with regular greedy fill)
// to further improve the groups.
// the whole process is repeated several times according to the given parameters.
//
// @throw GraphColoringException
//		if the data structures of the program are not in normal state.
//----------------------------------------------------------------------------
void GraphColoringManager::FillInitialChain()
{

	Chain* bestChain = NULL;
	Chain* tempChain = NULL;
	VertexDirectory* dir = NULL;
	VertexDirectory* bestDir = NULL;
	list<Group*>::iterator it;
	std::stringstream stream;
	for(int i=0; i < m_InputVars.numberOfIterationsToFillPermutaionChain; i++)
	{
		stream<<"Starting iteration #"<< i <<" of initial chain improvement";
		Logger::LogMessage(stream.str());
		stream.str("");

		//create a copy of the permutaion chain (from the static directory)
		try
		{
			dir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
			bestDir = new VertexDirectory(VertexDirectory::GetStaticCopyVertices());
		}
		catch(std::bad_alloc *e) //memory allocation failed
		{
			e = NULL;
			Logger::LogMessage("Unable to create backup directory in GraphColoringManager::FillInitialChain. application will terminate. ");
			return;			
		}
		tempChain = m_MainChain->CloneFromVertexDirectoryAndUpdateIt(dir);
		if (tempChain == NULL) // memory allocation failed
		{
			delete dir;
			Logger::LogMessage("Unable to create backup chain in GraphColoringManager::FillInitialChain. application will terminate. ");
			return;	
		}

		//fill the groups in the chain with greedy algorithm
		for(it = tempChain->Begin(); it != tempChain->End(); it++) 
		{
			stream<<"Trying to use Greedy Algorithm to fill group "<< (*it)->GetGroupName();
			Logger::LogMessage(stream.str());
			stream.str("");

			try
			{
				GreedyFillGroupAlgorithm::FillSingles(*(tempChain->GetGraph()),**it, tempChain->GetDirectory());
			}
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}
			
			//the group we worked on has changed, we need to updated the chain 
			//grapgh acordingly
			tempChain->GetGraph()->RemoveGroupVerticesFromGraph(*it);
			
			Logger::LogMessage("------------------------------------------------");
		}
		
		if (ChainSanityCheck(tempChain, false) == false)
			throw (new GraphColoringException("Sanity Check failed in fill Initial Chain"));

		//improve the groups with breaking algorithm
		for(it = tempChain->Begin(); it != tempChain->End(); it++) 
		{
			stream<<"Trying to use breaking algorithm to fill group "<< (*it)->GetGroupName();
			Logger::LogMessage(stream.str());
			stream.str("");

			int numberOfBreakingIterations = (*it)->Size() < m_InputVars.breakingIterationsGroupSize ? 1 : 2;
			try
			{
				BreakAndRefillGroupAlgorithm::BreakAndRefill(
					*(tempChain->GetGraph()),
					**it,
					numberOfBreakingIterations,
					m_InputVars.breakingPercentage,
					100,	// percentOfVerticesToStartImprovedGreedy - irelevnt we want to run regular greedy only
					100,	// percentOfVerticesToStopImprovedGreedy - irelevnt we want to run regular greedy only
					0,  	// numberOfPairsInImprovedGreedy - irelevnt we want to run regular greedy only
					tempChain->GetDirectory());
			}
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}

			tempChain->GetGraph()->RemoveGroupVerticesFromGraph(*it);
			Logger::LogMessage("------------------------------------------------");
		}
		
		if (ChainSanityCheck(tempChain, false) == false)
			throw (new GraphColoringException("Sanity Check failed in fill Initial Chain"));

		//if the new chain is better then the previes one, keep it.
		if(bestChain==NULL || tempChain->Compare(bestChain) == 1) //we found a better chain
		{	
			Logger::LogMessage("Saving improved chain");
			delete bestChain;
			bestChain = tempChain->CloneFromVertexDirectoryAndUpdateIt(bestDir);
		}
		else
		{
			Logger::LogMessage("Staying with previous chain");
		}

		delete dir;
		delete tempChain;
		
		Logger::LogMessage("------------------------------------------------");
	}

	if (ChainSanityCheck(bestChain, true) == false)
			throw (new GraphColoringException("Sanity Check failed in fill Initial Chain"));
	

	//update the main chain to the best result (use the ststic directory)
	delete m_MainChain; // dump the original chain
	m_MainChain = bestChain->CloneFromVertexDirectoryAndUpdateIt(NULL); //asgin the new filled chain
	delete bestChain;
	delete bestDir;

	if (ChainSanityCheck(m_MainChain, true) == false)
		throw (new GraphColoringException("Sanity Check failed in fill Initial Chain"));

	OutputIntermediateResult();

	Logger::LogMessage("Done filling initial chain");
	Logger::LogMessage("###############################################################");
}

//----------------------------------------------------------------------------
// StartTheColoring
// adds groups to the chain and improve the chain in order to achieve 
// a coloring of the graph (division of the graph to independent disjoint groups).
// 
// the groups that are added can be improved using the following algorithms:
// 1. regular greedy algorithm
// 2. improved greedy algorithm (works on couples of vertices)
// 3. interleaving of both kinds of greedy algorithms.
// 4. breaking the group (return some of its vertices to the graph)
//		and running algorithm 3 on the broken group.
// 
// after improving the single group with the above algorithms, we try to improve
// the whole chain. for this we use three types of algorithms:
// 5. switch singles
// 6. switch couples
// 7. dump groups (note: in current version this algorithm is not yet implemented)
//
// when we finish adding a group and improving the chain we compare the result
// to the destination chain given as part of the program input.
// if we managed to improve, we continue to add groups 
// if not - we roll back the current result and try again.
//
// @param algorithm
//		a bit-map of the algorithms we want to run on the chain and groups.
//
// @return COLORING_RESULT
//		IMPROVED -	 if the function finished and found an improved coloring
//		UNIMPROVED - if there are no more retries left and the function 
//					 was unable to improve the given chain.
//		BROKEN -	 if the program encountered a problem 
//					(such as data structures in not-normal state)
//----------------------------------------------------------------------------
GraphColoringManager::COLORING_RESULT GraphColoringManager::StartTheColoring(ALGORITHMS algorithm)
{
	int numberOftries = NUMBER_OF_TRIES_TO_FILL_CHAIN;
	bool bAddGroups=true;
	VertexDirectory* workingDir = NULL;
	VertexDirectory* backupDir  = NULL;
	
	try
	{
		workingDir = new VertexDirectory(this->m_MainChain->GetDirectory()->GetStaticCopyVertices());
		backupDir = new VertexDirectory(this->m_MainChain->GetDirectory()->GetStaticCopyVertices());
	}
	catch(std::bad_alloc *e) //memory allocation failed
	{
		e = NULL;
		Logger::LogMessage("Unable to create backup directory in GraphColoringManager::StartTheColoring. application will terminate. ");
		return BROKEN;			
	}

	Chain* workingChain = m_MainChain->CloneFromVertexDirectoryAndUpdateIt(workingDir);
	Chain* backupChain = m_MainChain->CloneFromVertexDirectoryAndUpdateIt(backupDir);
	if (workingChain == NULL || backupChain == NULL) // memory allocation failed
	{
		Logger::LogMessage("Unable to create backup chain in GraphColoringManager::StartTheColoring. application will terminate. ");
		return BROKEN;	
	}

	while (bAddGroups)
	{
		Logger::LogMessage("Adding next group to chain");
		//check the index of the current group and turn off some of the algorithmes if needed
		if(m_MainChain->GetLength() == m_InputVars.maxIndexForOptimizations)
		{
			Logger::LogMessage("Reached max index for optimization, stopping dump and refill");
			Logger::LogMessage("------------------------------------------------");
			algorithm = (algorithm & !DUMP_GROUPS_AND_REFILL);
		}
		if(m_MainChain->GetLength() == m_InputVars.fastMode)
		{
			Logger::LogMessage("Starting fast mode");
			Logger::LogMessage("------------------------------------------------");
			
			//TODO what are the algorithmes we are activating in fast mode?
			//algorithms to turn off:
			algorithm = (algorithm & 	!SWITCH_PAIRS				&
										!BREAK_AND_REFILL			&	  
										!IMPROVE_GROUP_WITH_GREEDY  );
			//algorithms to turn on:
			algorithm = (algorithm |	GREEDY );								
		}
		
		//check if we are done filling this chain 
		if(	m_MainChain->GetLength() == m_InputVars.destinationChainSize ||
			m_MainChain->GetGraph()->Count() == 0 )
		{
			algorithm = algorithm & !ALL; //turn off all algorithmes
			bAddGroups = false;
			break;
		}

		//now, try to add a new group to the chain
		int nextGroupInChainIndex = m_MainChain->GetNextGroupIndex();
		Group *tempGroup = NULL;
		Group *groupToAdd = NULL;
		try
		{
			tempGroup = new Group(nextGroupInChainIndex, workingDir);
			workingChain->AddGroup(tempGroup);
			groupToAdd = new Group(nextGroupInChainIndex, NULL);
			m_MainChain->AddGroup(groupToAdd);
		}
		catch(std::bad_alloc *e) // memory allocation failed
		{
			e = NULL;
			Logger::LogMessage("Fatal Exepetion. application will terminate. ");
			return BROKEN;
		}

		if(algorithm & GREEDY)
		{
			try
			{
				GreedyFillGroupAlgorithm::FillSingles(	*(workingChain->GetGraph()),
														*tempGroup,
														workingChain->GetDirectory());
			}
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}
			
			Logger::LogMessage("------------------------------------------------");

			if (GroupSanityCheck(tempGroup, workingChain) == false)
			{
				Logger::LogMessage("Sanity Check failed in coloring");
				return BROKEN;
			}
		}

		if(algorithm & IMPROVED_GREEDY)
		{
			try
			{
				GreedyFillGroupAlgorithm::FillCouples(	*(workingChain->GetGraph()),
													*tempGroup, 
													workingChain->GetDirectory());
			}
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}
			Logger::LogMessage("------------------------------------------------");
			
			if (GroupSanityCheck(tempGroup, workingChain) == false)
			{
				Logger::LogMessage("Sanity Check failed in coloring");
				return BROKEN;
			}
		}

		if(algorithm & IMPROVE_GROUP_WITH_GREEDY)
		{
			try
			{
				GreedyFillMaximalGroupAlgorithm::Fill(
					*(workingChain->GetGraph()),
					*tempGroup, 
					m_InputVars.numberOfIterationsForGreedySearch,
					m_InputVars.percentOfVerticesToStartImprovedGreedy,
					m_InputVars.percentOfVerticesToStopImprovedGreedy,
					m_InputVars.numberOfPairsInImprovedGreedy,
					workingChain->GetDirectory(),
					false); //true == before we start the singles-couples, we try only singles
			}
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}
			Logger::LogMessage("------------------------------------------------");

			if (GroupSanityCheck(tempGroup, workingChain) == false)
			{
				Logger::LogMessage("Sanity Check failed in coloring");
				return BROKEN;
			}

			if (GroupSanityCheck(groupToAdd, m_MainChain) == false)
			{
				Logger::LogMessage("Sanity Check failed in coloring");
				return BROKEN;
			}
		}


		if(algorithm & BREAK_AND_REFILL)
		{
			int numberOfBreakingIterations = tempGroup->Size() < m_InputVars.breakingIterationsGroupSize ? 1 : 2;

			try
			{
				BreakAndRefillGroupAlgorithm::BreakAndRefill(
					*(workingChain->GetGraph()),
					*tempGroup,
					numberOfBreakingIterations,
					m_InputVars.breakingPercentage,
					m_InputVars.percentOfVerticesToStartImprovedGreedy,
					m_InputVars.percentOfVerticesToStopImprovedGreedy,
					m_InputVars.numberOfPairsInImprovedGreedy,
					workingChain->GetDirectory());
			}
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}
			Logger::LogMessage("------------------------------------------------");

			if (GroupSanityCheck(tempGroup, workingChain) == false)
			{
				Logger::LogMessage("Sanity Check failed in coloring");
				return BROKEN;
			}
		}
		

		if (GroupSanityCheck(groupToAdd, m_MainChain) == false)
		{
			Logger::LogMessage("Sanity Check failed in coloring");
			return BROKEN;
		}

		//the new group is full from greedy algorithms or empty if they were skipped.
		//in any case they are already part of their destained chain.
		//we now update the matching graphs for the next alogorithmes.
		Algorithms::UpdateGraphAndGroupFromCopies(*(m_MainChain->GetGraph()), *groupToAdd, *tempGroup);
		workingChain->GetGraph()->RemoveGroupVerticesFromGraph(tempGroup);

		if (GroupSanityCheck(groupToAdd, m_MainChain) == false)
		{
			Logger::LogMessage("Sanity Check failed in coloring");
			return BROKEN;
		}
		
		OutputIntermediateResult();

		if(algorithm & SWITCH_SINGELS)
		{
			try
			{
				SwitchVerticesAlgorithm switchAlg(workingChain);
				switchAlg.SwitchSingles();
				if(workingChain->Compare(m_MainChain) > 0)
				{
					//update the main chain to the new result (use the static directory)
					delete m_MainChain; // dump the original chain
					m_MainChain = workingChain->CloneFromVertexDirectoryAndUpdateIt(NULL);

					if(ChainSanityCheck(m_MainChain, false) == false)
					{
						Logger::LogMessage("Sanity Check failed in coloring");
						return BROKEN;
					}
				}
				else
				{
					Logger::LogMessage("Rolling back switch singles");
					//rollback the temp chain to the previous result
					delete workingChain; // dump the current temp chain
					workingChain = m_MainChain->CloneFromVertexDirectoryAndUpdateIt(workingDir);

					if(ChainSanityCheck(workingChain, false) == false)
					{
						Logger::LogMessage("Sanity Check failed in coloring");
						return BROKEN;
					}
				}
			}			
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}
			Logger::LogMessage("------------------------------------------------");
		}

		
		if(algorithm & SWITCH_PAIRS)
		{
			try
			{
				SwitchVerticesAlgorithm switchAlg(workingChain);
				switchAlg.SwitchCouples();
				if(workingChain->Compare(m_MainChain) > 0)
				{
					//update the main chain to the new result (use the static directory)
					delete m_MainChain; // dump the original chain
					m_MainChain = workingChain->CloneFromVertexDirectoryAndUpdateIt(NULL);

					if(ChainSanityCheck(m_MainChain, false) == false)
					{
						Logger::LogMessage("Sanity Check failed in coloring");
						return BROKEN;
					}
				}
				else
				{
					Logger::LogMessage("Rolling back switch couples");
					//rollback the temp chain to the previous result
					delete workingChain; // dump the current temp chain
					workingChain = m_MainChain->CloneFromVertexDirectoryAndUpdateIt(workingDir);

					if(ChainSanityCheck(workingChain, false) == false)
					{
						Logger::LogMessage("Sanity Check failed in coloring");
						return BROKEN;
					}
				}
			}
			catch(GraphColoringException *e)
			{
				Logger::LogMessage(e->GetErrorDescription());
			}
			Logger::LogMessage("------------------------------------------------");
		}
		
		if(algorithm & DUMP_GROUPS_AND_REFILL)
		{
			{
				//run the algorithm		
				Logger::LogMessage("DUMP_GROUPS_AND_REFILL - not implemnted yet");
			}
			Logger::LogMessage("------------------------------------------------");
		}


		if(ChainSanityCheck(m_MainChain, true) == false)
		{
			Logger::LogMessage("Sanity Check failed in coloring");
			return BROKEN;
		}

		OutputIntermediateResult();

		//check if the chain is better than the destination chain
		int len =	m_MainChain->GetLength() < m_InputVars.numberOfGroupsInDestinationColoring ? 
					m_MainChain->GetLength() : m_InputVars.numberOfGroupsInDestinationColoring; 
		int res = m_MainChain->Compare(m_InputVars.destinationColoring, len); 
		if(res < 0 || (res==0 && m_InputVars.improvedColoringOnly))
		{
			Logger::LogMessage("Chain found is not as good as previous chain");
			//the chain we found is not good enough
			numberOftries--;
			
			//we tried enough times, this calculation is fruitless
			if(numberOftries <= 0)
				return UNIMPROVED;
			
			//dump the result and roll back to the previous chain
			delete m_MainChain;
			m_MainChain = backupChain->CloneFromVertexDirectoryAndUpdateIt(NULL);
		}
		else
		{
			// we have a good thing going on ...
			// re-start the counter and update the backup
			numberOftries = NUMBER_OF_TRIES_TO_FILL_CHAIN;
			delete backupChain;
			backupChain = m_MainChain->CloneFromVertexDirectoryAndUpdateIt(backupDir);
		}

		Logger::LogMessage("###############################################################");
	}

	//we finished adding groups to the chain, and manged to improve the coloring
	return IMPROVED;
}

//----------------------------------------------------------------------------
// OutputResult
// writes the coloring result to a file.
// the file name will be the input chain file name with a different file ending
// (replacing the .chain ending).
// If the coloring is legal the ending will be .coloring ending.
// if we have a legal chain (partial or final) that is not 
// a full and improved coloring of the graph the ending will be .result
// In case the coloring is not legal(broken data structures) a .broken ending.
//
// @param chainFileName
//		the name of the input chain file.
// @param coloringResult
//		IMPROVED -   if we have a legal and improved coloring we want to print to the file
//		UNIMPROVED - if we have a legal chain (partial or final) that is not
//					 a full and improved coloring of the graph.
//		BROKEN - 	 if we have an illegal chain.
//----------------------------------------------------------------------------
void GraphColoringManager::OutputResult(string chainFileName, COLORING_RESULT coloringResult)
{	
	Logger::LogMessage("Saving result");
	//prepare the output file name, based on the input file name
	string outputFileName = CleanNameStr(chainFileName);
	/*int pos = outputFileName.find_last_of(".");
	if(pos != string::npos)
		outputFileName.erase(pos);*/
	
	if(coloringResult == IMPROVED)
	{
		Logger::LogMessage("application found an improved coloring for the given chain");
		outputFileName += ".coloring";
	}
	else if(coloringResult == UNIMPROVED)
	{
		Logger::LogMessage("application will produce intermidate output");
		outputFileName += ".result";
	}
	else // coloringResult == BROKEN
	{
		Logger::LogMessage("data structuers were broken during application execution");
		outputFileName += ".broken";
	}

	ChainWriter writer(outputFileName);
	writer.SetBinaryWordLength(m_InputVars.n);
	writer.SetBinaryWordWeight(m_InputVars.w);
	writer.SetNumberOfGroups(m_MainChain->GetLength());
	
	//calculate the group size array:
	int *groupSizes = NULL;
	try
	{
		groupSizes = new int[m_MainChain->GetLength()];
	}
	catch(std::bad_alloc *e)
	{
		Logger::LogMessage("memory allocation failed. unable to produce application output");
		e = NULL;
		return;
	}

	list<Group*>::iterator it = m_MainChain->Begin();
	//TODO do we need to sort the list or is it alrady sorted?
	for(int i=0; i < m_MainChain->GetLength(); i++, it++)
	{
		groupSizes[i] = (*it)->Size();
	}
	writer.SetGroupSummary("all groups sizes", groupSizes);

	it = m_MainChain->Begin();
	for(; it != m_MainChain->End(); it++)
	{
		list<VertexKey> groupVertices = (*it)->VerticesNames();
		if(groupVertices.empty())
		{
			VertexKey* dummyVertex = NULL;
			try
			{
				dummyVertex = new VertexKey();
			}
			catch(std::bad_alloc *e)
			{
				Logger::LogMessage("memory allocation failed. unable to produce application output");
				e = NULL;
				return;
			}

			for(int i=0; i < m_InputVars.n; i++)
			{
				dummyVertex->push_back(0);
			}
			writer.SetFirstVertex((*it)->GetGroupName(), dummyVertex);
		}
		else
		{
			list<VertexKey>::iterator groupIt = groupVertices.begin();
			writer.SetFirstVertex((*it)->GetGroupName(), &(*groupIt));
			groupIt++;
			for(;groupIt != groupVertices.end(); groupIt++)
			{
				writer.SetNextVertex(&(*groupIt));
			}
		}
		

	}

	Logger::LogMessage("###############################################################");
}

//----------------------------------------------------------------------------
// ChainSanityCheck
// make sure data structures of the chain are in correct state
//
// @param chainToCheck
//		a pointer to a chain object whose data structures we want to check
// @param isFullCheck
//		true - if we want to perform all the checks
//		false if we want to skip some of the checks.
//
// @return bool
//		true - if the chain given passed all the checks
//		false - if a check has failed
//----------------------------------------------------------------------------
bool GraphColoringManager::ChainSanityCheck(Chain *chainToCheck, bool isFullCheck)
{
	if(	chainToCheck == NULL)
	{
		Logger::LogMessage("failed sanity check! NULL chain recived");
		return false;
	}

	if(!Algorithms::ValidateAllGroupsAreIndependent(chainToCheck))
	{
		Logger::LogMessage("failed sanity check! groups that are not independent found");
		return false;
	}

	if(!Algorithms::ValidateVertexDirectoryState(chainToCheck->GetGraph(), chainToCheck->ChainGroups(), 
		chainToCheck->ChainGroupNames(), chainToCheck->GetDirectory()))
	{
		Logger::LogMessage("failed sanity check! Vertex Directory is broken");
		return false;
	}

	if(isFullCheck)
	{
		list<Group*>::iterator it = chainToCheck->Begin();
		for(; it != chainToCheck->End(); it++)
		{
			if(!Algorithms::ValidateGroupInChainIsDisjoint(chainToCheck, (*it)))
			{
				Logger::LogMessage("failed sanity check! group in the chain is not disjoint");
				return false;
			}
		}
	}

	return true;
}

//----------------------------------------------------------------------------
// GroupSanityCheck
// make sure data structures of the group are in correct state in relation to 
// the given chain.
//
// @param groupToCheck
//		a pointer to a group object whose data structures we want to check
// @param relativeChain
//		the chain in relation to which we are performing the checks
//
// @return bool
//		true - if the group given passed all the checks
//		false - if a check has failed
//----------------------------------------------------------------------------
bool GraphColoringManager::GroupSanityCheck(Group * groupToCheck, Chain *relativeChain)
{
	if( groupToCheck == NULL || relativeChain == NULL)
	{
		Logger::LogMessage("failed sanity check! NULL group or NULL chain were passed");
		return false;
	}

	if(!Algorithms::ValidateGroupIsIndependent(groupToCheck))
	{
		Logger::LogMessage("failed sanity check! group passed is not independent");
		return false;
	}

	if(!Algorithms::ValidateGroupInChainIsDisjoint(relativeChain, groupToCheck))
	{
		Logger::LogMessage("failed sanity check! group passed is not disjoint from chain passed");
		return false;
	}

	if(!Algorithms::ValidateVertexDirectoryState(relativeChain->GetGraph(), relativeChain->ChainGroups(),
								relativeChain->ChainGroupNames(), relativeChain->GetDirectory()))
	{
		Logger::LogMessage("failed sanity check! Vertex Directory is broken");
		return false;
	}

	return true;
}

//----------------------------------------------------------------------------
// OutputIntermediateResult
// creates a file with the current information of the chain.
// the file name will be in the format: dd-mm_hh-mm_intermediate.result
//----------------------------------------------------------------------------
void GraphColoringManager::OutputIntermediateResult()
{
	string fileName = GetCurrentTime(true);
	fileName += "_intermediate";
	OutputResult(fileName, UNIMPROVED);
}

//----------------------------------------------------------------------------
// CleanNameStr
// removes from a given string all the characters before the last "\" 
// in the given string.
// and all the characters after the last "." in the given string.
// for example: 
// if the given string is: "a\b\c\ddd.txt" the return string will be: "ddd"
// if the string does not contain any "\" or "." nothing is done for it.
//
// @param strToClean
//		the string to remove characters from
//
// @return string
//		the string without the described characters.
//----------------------------------------------------------------------------
string GraphColoringManager::CleanNameStr(string strToClean)
{
//note! can only be used on windows platform.
#ifdef WIN32	
	int pos = strToClean.find_last_of('\\');
	if(pos != string::npos)
		strToClean = strToClean.substr(pos+1,strToClean.size());
	pos = strToClean.find_last_of('.');
	if(pos != string::npos)
		strToClean = strToClean.substr(0, pos);
	
	return strToClean;
#endif
}

/*****************************************************************************/
// general test and debugging funactions 
/*****************************************************************************/
#ifdef _DEBUG
//----------------------------------------------------------------------------
// forDebug_runUnitTests: run all graph coloring tests
//----------------------------------------------------------------------------
void forDebug_runUnitTests()
{
	//run all graph coloring tests 
	Debug::PrintDebugMsg("Running unit tests");
	RunGraphColoringTests();
	Debug::PrintDebugMsg("Done running unit tests");
	VertexDirectory::Clear();
}

//----------------------------------------------------------------------------
// forDebug_validateGraphState: runs tests to make sure the graph is valid:
// all vertices which the graph reports as in the graph, point to the graph etc.
//----------------------------------------------------------------------------
Chain* forDebug_validateGraphState(string chainFileName, InputVariables &inputVars,set<vector<bool> >* vertices)
{
	// check state was updated
	ChainParser chainFile(chainFileName);
	Debug::PrintDebugMsg("Loading chain from input");
	
	//create the chain
	Chain* chain = new Chain(chainFile, inputVars);
	Debug::PrintDebugMsg("Validating load was correct");
	Debug::PrintDebugMsg("Running ValidateGraphState.");
	TestUtils::PrintTestResult("ValidateGraphState", ValidateGraphState(inputVars.n, inputVars.w, chainFile, chain, vertices));
	Debug::PrintDebugMsg("Load validated");
	
	return chain;
}

//----------------------------------------------------------------------------
// forDebug_debugAlgorithems: a test for graph coloring algorithms
//----------------------------------------------------------------------------
void forDebug_debugAlgorithems(Chain* chain, InputVariables &inputVars )
{
	try 
	{
		Debug::PrintDebugMsg("Running algorithm for next group");
		// choose one of the following tests:
		int algorithm = 5;
		int startImprovingIndex = 1;
		int numberOfGroupsToFind = 1;
		// don't improve the newly-found group by breaking it
		TestUtils::PrintTestResult("FindNextGroupInChain", FindNextGroupInChain(inputVars.n, inputVars.w, algorithm, numberOfGroupsToFind, *chain, &inputVars, false));
		TestUtils::PrintTestResult("FindNextGroupInChain", FindNextGroupInChain(inputVars.n, inputVars.w, 6, numberOfGroupsToFind, *chain, &inputVars, false));
		Debug::PrintDebugMsg("Found chain: ");
		chain->PrintGroupData();
	}
	catch (GraphColoringException &e)
	{
		Debug::PrintDebugMsg("Exception: ");
		Debug::PrintDebugMsg(e.GetErrorDescription());
	}
	catch (exception e)
	{
		string errStr = "some other exception happened: ";
		errStr += e.what();
		Debug::PrintDebugMsg(errStr);
	}
}
#endif //_DEBUG
